/**
 * 
 */
package jp.co.wap.exam;

import java.util.Collection;
import java.util.Collections;
import java.util.List;
import jp.co.wap.exam.lib.Interval;


/**
 * @author pratibind_jha
 *
 */
public class Problem2 {
	
	public int getMaxWorkingTime(List<Interval> intervals) {
		
		//added the compare method in Interval class for sorting.
		//sort the interval by first finish time.
		Collections.sort(intervals, new Interval());
		
		/*for(Interval itv : intervals)
				System.out.println(itv.getEndHour()+":"+itv.getEndMinute()+ " "+ itv.getEndMinuteUnit());*/
		
		int len = intervals.size();
		int[] pvalues = new int[len+1];
		int[] maxResult = new int[len+1];
		
		//initialize the pvalues to 0
		pvalues[0] = 0;
		pvalues[1] = 0;
		for(int i=2;i<len+1;i++) {
			//System.out.println(intervals.get(i-1).getBeginMinuteUnit()+ "  " + intervals.get(i-2).getEndMinuteUnit());
			for(int j=i-2;j>=0;j--) {
				if(intervals.get(i-1).getBeginMinuteUnit() >= intervals.get(j).getEndMinuteUnit()) { 
					//System.out.println(intervals.get(i-1).getBeginMinuteUnit()+ "  " + intervals.get(j).getEndMinuteUnit());
					pvalues[i] = j+1;
					break;
				}	
			}
		}
		
		/*for(int i:pvalues)
				System.out.println(i);*/
	
		//compute the maximum time.
		maxResult[0] = 0;
		for(int i=1;i<len+1;i++) {
			maxResult[i] = maximum(intervals.get(i-1).getIntervalMinute()+maxResult[pvalues[i]],maxResult[i-1]);
			
		}
		
		return maxResult[len];
	}

	//utility function
	int maximum(int x, int y) {
		
		return ((x>y)?x:y);
	}
}

